{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "456a591a-6383-45cf-ac3e-cca3014edf6b",
   "metadata": {},
   "source": [
    "# Quantum Counting using the Iterative Quantum Amplitude Estimation Algorithm\n",
    "\n",
    "Quantum Counting algorithm [[1](#QCWiki)] is an algorithm for efficiently estimating the number of valid solutions to a search problem, based on the amplitude estimation algorithm. It demonstrates a quadratic improvement with regards to a classical algorithm with black-box oracle access to the function $f$.\n",
    "\n",
    "More precisely, the counting problem is, given a boolean function $f :\\{0, 1\\}^n\\rightarrow\\{0,1\\}$, estimate the number of inputs $x$ to $f$ such that $f(x)=1$.\n",
    "\n",
    "In this tutorial we will deomstrate how to estimate the Couting problem using a specific variant of the Amplitude Estimation algorithm - the Iterative Quantum Amplitude Estimation (IQAE) [[2](#IQAE)].\n",
    "\n",
    "The IQAE does not rely on the Quantum Phase Estimation algoritm [[3](#AE)], but purely on applications of the grover operator:\n",
    "$$\n",
    "Q\\equiv -  A S_0 A^{\\dagger} S_{\\psi_1} ,\n",
    "$$\n",
    "Hence reducing the required amount of qubits and gates of the circuit, at the expense of additional multiplicative factor poly-logarithmic in the error $\\epsilon$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38184f42-a77b-4370-8e42-0224e711c5e0",
   "metadata": {},
   "source": [
    "## Setting the problem\n",
    "\n",
    "We will choose the equation:\n",
    "$$\n",
    "(a + b) <= 2\n",
    "$$\n",
    "where $a$, $b$ are 2-bit unsigned integers. This equation has 6 solutions. The goal is to estimate the number of valid solutions out of the 16 possible inputs, with precision $0.5$.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d69d5803-107a-4083-aa25-9c3d5dc092f3",
   "metadata": {},
   "source": [
    "## Amplitude Estimation using Phase Estimation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58a44d55-97ee-4463-8d38-d3c64151f76a",
   "metadata": {},
   "source": [
    "We first show how to use Quantum Phase Estimation algorithm for the Quantum Counting [[3](#AE)], then move to solve it using the IQAE method."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91f9f567-6513-4249-b0ab-438f0e368976",
   "metadata": {},
   "source": [
    "Given a state $|\\psi\\rangle$ such that $|\\psi\\rangle=\\sqrt{a}|\\psi_1\\rangle+\\sqrt{1-a}|\\psi_0\\rangle$ we can measure $a$ up to arbitrary precision, given the following building blocks:\n",
    "1) State Preperation: \n",
    "A unitary $A$ such that: $A|0\\rangle = |\\psi\\rangle = \\sqrt{a}|\\psi_1\\rangle+\\sqrt{1-a}|\\psi_0\\rangle$\n",
    "\n",
    "\n",
    "2) Oracle:\n",
    "A unitary $S_{\\psi_1}$ such that $S_{\\psi_1}=I-2|\\psi_1\\rangle\\langle\\psi_1|$, which adds a $(-1)$ phase to $|\\psi_1|\\psi\\rangle\\rangle$ and does nothing to any orthognal states to $|\\psi_1\\rangle$.\n",
    "This is effectively a reflection around the \"good\" state $|\\psi_1\\rangle$.\n",
    "\n",
    "Given this 2 functions, we can construct the grover operator:\n",
    "$$\n",
    "Q\\equiv -  A S_0 A^{\\dagger} S_{\\psi_1} ,\n",
    "$$\n",
    "Which is exactly the same operator as the one for the grover's search algorithm. \n",
    "\n",
    "\n",
    "In the subspace spanned by $|\\psi_1\\rangle$ and $|\\psi_0\\rangle$, $Q$ has 2 eigenvalues: \n",
    "$$\n",
    "\\lambda_{\\pm}=\\exp\\left(\\pm i2\\pi \\theta \\right), \\qquad \\sin^2 \\left(\\pi \\theta\\right)\\equiv a.\n",
    "$$\n",
    "\n",
    "Therefore, if we apply a QPE on $A|0\\rangle$ we will have these two eigenvalues encoded in the QPE register, however, both give the value of $a$, so there is no ambiguity here."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16100fce-c9ad-4eba-a4a2-deb14a610b43",
   "metadata": {},
   "source": [
    "### Arithmetic oracle\n",
    "\n",
    "Here we define the $S_{\\psi_1}$ oracle:\n",
    "\n",
    "$$\n",
    "S_{\\psi_1}|a\\rangle|b\\rangle= (-1)^{f(a,b)}|a\\rangle|b\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "98a57228-2722-4be7-a40f-b15d990962d7",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:34:56.487006Z",
     "iopub.status.busy": "2024-05-07T14:34:56.486421Z",
     "iopub.status.idle": "2024-05-07T14:34:59.720025Z",
     "shell.execute_reply": "2024-05-07T14:34:59.719352Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq.qmod import H, QArray, QBit, QNum, Z, qfunc, within_apply\n",
    "\n",
    "A_SIZE = 2\n",
    "B_SIZE = 2\n",
    "DOMAIN_SIZE = A_SIZE + B_SIZE\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def arith_equation(a: QNum, b: QNum, res: QBit):\n",
    "    res ^= a + b <= 2\n",
    "\n",
    "\n",
    "# use phase kickback for turning the arith_equation to an oracle\n",
    "@qfunc\n",
    "def arith_oracle(a: QNum, b: QNum):\n",
    "    aux = QBit(\"aux\")\n",
    "    within_apply(\n",
    "        lambda: (allocate(1, aux), X(aux), H(aux)), lambda: arith_equation(a, b, aux)\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d259adad-9b69-4602-932b-97d98b546503",
   "metadata": {},
   "source": [
    "### Diffuser\n",
    "\n",
    "The diffuser consists of the reflection around the $|0\\rangle$ state, and a state-preparation function.\n",
    "\n",
    "The state preparation function $A$ reflects knowledge about the solution space, and can be used to eliminate invalid assignments. Here we assume no knowledge on the solution space, hence we use the uniform superposition state preparation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "33343f03-82cc-4808-9759-dd747fcd5209",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:34:59.723356Z",
     "iopub.status.busy": "2024-05-07T14:34:59.722580Z",
     "iopub.status.idle": "2024-05-07T14:34:59.728103Z",
     "shell.execute_reply": "2024-05-07T14:34:59.727531Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from classiq.qmod import (\n",
    "    QCallable,\n",
    "    U,\n",
    "    X,\n",
    "    apply_to_all,\n",
    "    bind,\n",
    "    control,\n",
    "    hadamard_transform,\n",
    "    invert,\n",
    "    within_apply,\n",
    ")\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def reflection_about_zero(x: QArray[QBit]):\n",
    "    lsb = QBit(\"lsb\")\n",
    "    msbs = QArray(\"msbs\", QBit, x.len - 1)\n",
    "\n",
    "    apply_to_all(X, x)\n",
    "    bind(x, [msbs, lsb])\n",
    "    control(msbs, lambda: Z(lsb))\n",
    "    bind([msbs, lsb], x)\n",
    "    apply_to_all(X, x)\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_diffuser(sp_operand: QCallable[QArray[QBit]], x: QArray[QBit]):\n",
    "    within_apply(\n",
    "        lambda: invert(lambda: sp_operand(x)),\n",
    "        lambda: reflection_about_zero(x),\n",
    "    )\n",
    "\n",
    "\n",
    "sp_oracle = lambda x: hadamard_transform(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26ccb4d1-030e-48dc-a883-908d0cd9359c",
   "metadata": {},
   "source": [
    "### Complete Grover operator definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "576af4f4-5243-4ec7-b754-55249b71ee59",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:34:59.730466Z",
     "iopub.status.busy": "2024-05-07T14:34:59.730288Z",
     "iopub.status.idle": "2024-05-07T14:34:59.733702Z",
     "shell.execute_reply": "2024-05-07T14:34:59.733080Z"
    }
   },
   "outputs": [],
   "source": [
    "@qfunc\n",
    "def my_grover_operator(\n",
    "    oracle_operand: QCallable[QArray[QBit]],\n",
    "    sp_operand: QCallable[QArray[QBit]],\n",
    "    x: QArray[QBit],\n",
    "):\n",
    "    oracle_operand(x)\n",
    "    my_diffuser(sp_operand, x)\n",
    "    U(0, 0, 0, np.pi, x[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75227dd9-12f9-4933-909d-795c9bdeff2d",
   "metadata": {},
   "source": [
    "### Wrap all to the Phase Estimation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "372e2c83-9cc3-45fc-bdb4-ccd1db54a2c3",
   "metadata": {},
   "source": [
    "We will acheive the desired precision only in the IQAE phase. Here we compute the worst-case precision for 5 phase qubits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "71ee226b-f8f1-4a31-ad51-ffa6cb29acfc",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:34:59.736198Z",
     "iopub.status.busy": "2024-05-07T14:34:59.735832Z",
     "iopub.status.idle": "2024-05-07T14:34:59.742523Z",
     "shell.execute_reply": "2024-05-07T14:34:59.741853Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5681439279637468"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NUM_PHASE_QUBITS = 5\n",
    "\n",
    "x = np.linspace(0, 1, 100)\n",
    "(2**DOMAIN_SIZE) * max(\n",
    "    np.abs(\n",
    "        np.sin(np.pi * x) ** 2 - np.sin(np.pi * (x - 1 / (2**NUM_PHASE_QUBITS))) ** 2\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "31162825-bdb0-4b71-98be-fde318dfbf4a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:34:59.744995Z",
     "iopub.status.busy": "2024-05-07T14:34:59.744475Z",
     "iopub.status.idle": "2024-05-07T14:34:59.749032Z",
     "shell.execute_reply": "2024-05-07T14:34:59.748453Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq.qmod import Output, allocate, allocate_num, qpe\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(\n",
    "    phase_reg: Output[QNum],\n",
    ") -> None:\n",
    "    state_reg = QArray(\"state_reg\")\n",
    "    allocate(DOMAIN_SIZE, state_reg)\n",
    "    allocate_num(NUM_PHASE_QUBITS, False, NUM_PHASE_QUBITS, phase_reg)\n",
    "    sp_oracle(state_reg)\n",
    "    qpe(\n",
    "        unitary=lambda: my_grover_operator(\n",
    "            lambda x: arith_oracle(x[0:A_SIZE], x[A_SIZE : x.len]),\n",
    "            sp_oracle,\n",
    "            state_reg,\n",
    "        ),\n",
    "        phase=phase_reg,\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23e1bba3-1958-4de1-aa5b-ea36842541c0",
   "metadata": {},
   "source": [
    "### Synthesize the model to a quantum program"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "2904fd77-dfb3-4a00-9400-e74316950f91",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:34:59.751186Z",
     "iopub.status.busy": "2024-05-07T14:34:59.751013Z",
     "iopub.status.idle": "2024-05-07T14:36:48.963805Z",
     "shell.execute_reply": "2024-05-07T14:36:48.963109Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/13914c60-4e29-4db8-93fc-00c519609d56?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import Constraints, create_model, show, synthesize, write_qmod\n",
    "\n",
    "constraints = Constraints(max_width=14)\n",
    "qmod_qpe = create_model(main, constraints=constraints)\n",
    "write_qmod(qmod_qpe, \"quantum_counting_qpe\")\n",
    "qprog_qpe = synthesize(qmod_qpe)\n",
    "show(qprog_qpe)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5fe6073e-4ebe-438c-b8bb-12d658c4eece",
   "metadata": {},
   "source": [
    "### Quantum Program execution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "7d2bed5b-b94b-4ed8-855a-675b92de5324",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:48.966558Z",
     "iopub.status.busy": "2024-05-07T14:36:48.965971Z",
     "iopub.status.idle": "2024-05-07T14:36:56.594710Z",
     "shell.execute_reply": "2024-05-07T14:36:56.594089Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import execute\n",
    "\n",
    "res = execute(qprog_qpe).result()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9cc9df6d-2968-4d3d-9ed8-5303336a1365",
   "metadata": {},
   "source": [
    "Plotting the resulting histogram we see two phase values with high probability (however, both corresponds to the same amplitude). Note that `phase_reg` is already coded as fixed QNum in the range [0,1]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "cbfd0b33-7448-4fd3-843b-c74b09d47c8d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.597597Z",
     "iopub.status.busy": "2024-05-07T14:36:56.597079Z",
     "iopub.status.idle": "2024-05-07T14:36:56.780530Z",
     "shell.execute_reply": "2024-05-07T14:36:56.779834Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "phase with max probability:  0.78125\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAigAAAGlCAYAAADQyw0eAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuNSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/xnp5ZAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAon0lEQVR4nO3df3RU9Z3/8Vd+kIEAkxggmUQSwJ8hQgDBhqmWpRATQqSwxD0FWcBdFg40eApRivGLKGgNpW6xuPzYVRC6JcXSg7qEX0Zcgh6GH6ZliVBSQWzigUlUlgzEZRKS+f7Rwz2dAuqEDPOZ+Hycc8/h3s/n3vu+n3OGeeX+mgifz+cTAACAQSJDXQAAAMDfIqAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIwTHeoC2qK1tVVnzpxR9+7dFREREepyAADAN+Dz+XThwgWlpKQoMvKrz5GEZUA5c+aMUlNTQ10GAABog9raWvXu3fsr+4RlQOnevbukvxyg3W4PcTUAAOCb8Hg8Sk1Ntb7Hv0pYBpQrl3XsdjsBBQCAMPNNbs/gJlkAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGOeGAsqyZcsUERGhefPmWcsuXbqkwsJC9ejRQ926dVNBQYHq6ur81qupqVF+fr5iY2OVmJioBQsW6PLlyzdSCgAA6EDaHFAOHz6sf//3f1dmZqbf8vnz52vbtm3asmWLKioqdObMGU2cONFqb2lpUX5+vpqamrR//35t3LhRGzZs0OLFi9t+FAAAoENpU0C5ePGipkyZoldeeUW33HKLtbyhoUHr1q3TL37xC40aNUpDhw7Va6+9pv379+vAgQOSpLffflvHjx/Xr3/9aw0ePFh5eXl67rnntGrVKjU1NbXPUQEAgLAW3ZaVCgsLlZ+fr+zsbD3//PPW8srKSjU3Nys7O9talp6errS0NLlcLg0fPlwul0sDBw5UUlKS1Sc3N1dz5szRsWPHNGTIkKv25/V65fV6rXmPx9OWsgEAN1HfJ7eHuoSAfLIsP9Ql4K8EHFA2b96s3//+9zp8+PBVbW63WzExMYqPj/dbnpSUJLfbbfX563Bypf1K27WUlJRoyZIlgZYKAADCVECXeGpra/XjH/9YmzZtUufOnYNV01WKi4vV0NBgTbW1tTdt3wAA4OYLKKBUVlaqvr5e9957r6KjoxUdHa2KigqtXLlS0dHRSkpKUlNTk86fP++3Xl1dnRwOhyTJ4XBc9VTPlfkrff6WzWaT3W73mwAAQMcVUEAZPXq0qqqqdOTIEWsaNmyYpkyZYv27U6dO2rNnj7VOdXW1ampq5HQ6JUlOp1NVVVWqr6+3+pSXl8tutysjI6OdDgsAAISzgO5B6d69uwYMGOC3rGvXrurRo4e1fMaMGSoqKlJCQoLsdrsee+wxOZ1ODR8+XJKUk5OjjIwMTZ06VcuXL5fb7daiRYtUWFgom83WTocFAADCWZue4vkqK1asUGRkpAoKCuT1epWbm6vVq1db7VFRUSorK9OcOXPkdDrVtWtXTZ8+XUuXLm3vUgAAQJiK8Pl8vlAXESiPx6O4uDg1NDRwPwoAGIrHjPG3Avn+5rd4AACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGCc61AUAf63vk9tDXcI39smy/FCXAAAdFmdQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGCcgALKmjVrlJmZKbvdLrvdLqfTqZ07d1rtI0eOVEREhN80e/Zsv23U1NQoPz9fsbGxSkxM1IIFC3T58uX2ORoAANAhBPRjgb1799ayZct05513yufzaePGjRo/frz+8Ic/6J577pEkzZw5U0uXLrXWiY2Ntf7d0tKi/Px8ORwO7d+/X2fPntW0adPUqVMnvfDCC+10SAAAINwFFFDGjRvnN//Tn/5Ua9as0YEDB6yAEhsbK4fDcc313377bR0/flzvvPOOkpKSNHjwYD333HNauHChnn32WcXExLTxMAAAQEfS5ntQWlpatHnzZjU2NsrpdFrLN23apJ49e2rAgAEqLi7Wl19+abW5XC4NHDhQSUlJ1rLc3Fx5PB4dO3bsuvvyer3yeDx+EwAA6LgCOoMiSVVVVXI6nbp06ZK6deumN954QxkZGZKkRx55RH369FFKSoqOHj2qhQsXqrq6Wlu3bpUkud1uv3AiyZp3u93X3WdJSYmWLFkSaKkAACBMBRxQ7r77bh05ckQNDQ363e9+p+nTp6uiokIZGRmaNWuW1W/gwIFKTk7W6NGjderUKd1+++1tLrK4uFhFRUXWvMfjUWpqapu3BwAAzBbwJZ6YmBjdcccdGjp0qEpKSjRo0CD98pe/vGbfrKwsSdLJkyclSQ6HQ3V1dX59rsxf774VSbLZbNaTQ1cmAADQcd3we1BaW1vl9Xqv2XbkyBFJUnJysiTJ6XSqqqpK9fX1Vp/y8nLZ7XbrMhEAAEBAl3iKi4uVl5entLQ0XbhwQaWlpdq7d692796tU6dOqbS0VGPHjlWPHj109OhRzZ8/XyNGjFBmZqYkKScnRxkZGZo6daqWL18ut9utRYsWqbCwUDabLSgHCAAAwk9AAaW+vl7Tpk3T2bNnFRcXp8zMTO3evVsPPvigamtr9c477+ill15SY2OjUlNTVVBQoEWLFlnrR0VFqaysTHPmzJHT6VTXrl01ffp0v/emAAAABBRQ1q1bd9221NRUVVRUfO02+vTpox07dgSyWwAA8C3Db/EAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMEFFDWrFmjzMxM2e122e12OZ1O7dy502q/dOmSCgsL1aNHD3Xr1k0FBQWqq6vz20ZNTY3y8/MVGxurxMRELViwQJcvX26fowEAAB1CQAGld+/eWrZsmSorK/XBBx9o1KhRGj9+vI4dOyZJmj9/vrZt26YtW7aooqJCZ86c0cSJE631W1palJ+fr6amJu3fv18bN27Uhg0btHjx4vY9KgAAENYifD6f70Y2kJCQoJ///Od6+OGH1atXL5WWlurhhx+WJJ04cUL9+/eXy+XS8OHDtXPnTj300EM6c+aMkpKSJElr167VwoUL9dlnnykmJuYb7dPj8SguLk4NDQ2y2+03Uj4M0/fJ7aEu4Rv7ZFl+qEsAjBZOn2eJz/TNEMj3d5vvQWlpadHmzZvV2Ngop9OpyspKNTc3Kzs72+qTnp6utLQ0uVwuSZLL5dLAgQOtcCJJubm58ng81lmYa/F6vfJ4PH4TAADouAIOKFVVVerWrZtsNptmz56tN954QxkZGXK73YqJiVF8fLxf/6SkJLndbkmS2+32CydX2q+0XU9JSYni4uKsKTU1NdCyAQBAGAk4oNx99906cuSIDh48qDlz5mj69Ok6fvx4MGqzFBcXq6GhwZpqa2uDuj8AABBa0YGuEBMTozvuuEOSNHToUB0+fFi//OUv9cMf/lBNTU06f/6831mUuro6ORwOSZLD4dChQ4f8tnflKZ8rfa7FZrPJZrMFWioAAAhTN/welNbWVnm9Xg0dOlSdOnXSnj17rLbq6mrV1NTI6XRKkpxOp6qqqlRfX2/1KS8vl91uV0ZGxo2WAgAAOoiAzqAUFxcrLy9PaWlpunDhgkpLS7V3717t3r1bcXFxmjFjhoqKipSQkCC73a7HHntMTqdTw4cPlyTl5OQoIyNDU6dO1fLly+V2u7Vo0SIVFhZyhgQAAFgCCij19fWaNm2azp49q7i4OGVmZmr37t168MEHJUkrVqxQZGSkCgoK5PV6lZubq9WrV1vrR0VFqaysTHPmzJHT6VTXrl01ffp0LV26tH2PCgAAhLUbfg9KKPAelI4rnN6bwDsTgK8WTp9nic/0zXBT3oMCAAAQLAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4AQWUkpIS3XffferevbsSExM1YcIEVVdX+/UZOXKkIiIi/KbZs2f79ampqVF+fr5iY2OVmJioBQsW6PLlyzd+NAAAoEOIDqRzRUWFCgsLdd999+ny5ct66qmnlJOTo+PHj6tr165Wv5kzZ2rp0qXWfGxsrPXvlpYW5efny+FwaP/+/Tp79qymTZumTp066YUXXmiHQwIAAOEuoICya9cuv/kNGzYoMTFRlZWVGjFihLU8NjZWDofjmtt4++23dfz4cb3zzjtKSkrS4MGD9dxzz2nhwoV69tlnFRMT04bDAAAAHckN3YPS0NAgSUpISPBbvmnTJvXs2VMDBgxQcXGxvvzyS6vN5XJp4MCBSkpKspbl5ubK4/Ho2LFj19yP1+uVx+PxmwAAQMcV0BmUv9ba2qp58+bp/vvv14ABA6zljzzyiPr06aOUlBQdPXpUCxcuVHV1tbZu3SpJcrvdfuFEkjXvdruvua+SkhItWbKkraUCAIAw0+aAUlhYqA8//FDvv/++3/JZs2ZZ/x44cKCSk5M1evRonTp1Srfffnub9lVcXKyioiJr3uPxKDU1tW2FAwAA47XpEs/cuXNVVlam//7v/1bv3r2/sm9WVpYk6eTJk5Ikh8Ohuro6vz5X5q9334rNZpPdbvebAABAxxVQQPH5fJo7d67eeOMNvfvuu+rXr9/XrnPkyBFJUnJysiTJ6XSqqqpK9fX1Vp/y8nLZ7XZlZGQEUg4AAOigArrEU1hYqNLSUr311lvq3r27dc9IXFycunTpolOnTqm0tFRjx45Vjx49dPToUc2fP18jRoxQZmamJCknJ0cZGRmaOnWqli9fLrfbrUWLFqmwsFA2m639jxAAAISdgM6grFmzRg0NDRo5cqSSk5Ot6fXXX5ckxcTE6J133lFOTo7S09P1+OOPq6CgQNu2bbO2ERUVpbKyMkVFRcnpdOof//EfNW3aNL/3pgAAgG+3gM6g+Hy+r2xPTU1VRUXF126nT58+2rFjRyC7BgAA3yL8Fg8AADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAME5AAaWkpET33XefunfvrsTERE2YMEHV1dV+fS5duqTCwkL16NFD3bp1U0FBgerq6vz61NTUKD8/X7GxsUpMTNSCBQt0+fLlGz8aAADQIQQUUCoqKlRYWKgDBw6ovLxczc3NysnJUWNjo9Vn/vz52rZtm7Zs2aKKigqdOXNGEydOtNpbWlqUn5+vpqYm7d+/Xxs3btSGDRu0ePHi9jsqAAAQ1iJ8Pp+vrSt/9tlnSkxMVEVFhUaMGKGGhgb16tVLpaWlevjhhyVJJ06cUP/+/eVyuTR8+HDt3LlTDz30kM6cOaOkpCRJ0tq1a7Vw4UJ99tlniomJ+dr9ejwexcXFqaGhQXa7va3lw0B9n9we6hK+sU+W5Ye6BMBo4fR5lvhM3wyBfH/f0D0oDQ0NkqSEhARJUmVlpZqbm5WdnW31SU9PV1pamlwulyTJ5XJp4MCBVjiRpNzcXHk8Hh07duya+/F6vfJ4PH4TAADouNocUFpbWzVv3jzdf//9GjBggCTJ7XYrJiZG8fHxfn2TkpLkdrutPn8dTq60X2m7lpKSEsXFxVlTampqW8sGAABhoM0BpbCwUB9++KE2b97cnvVcU3FxsRoaGqyptrY26PsEAAChE92WlebOnauysjLt27dPvXv3tpY7HA41NTXp/PnzfmdR6urq5HA4rD6HDh3y296Vp3yu9PlbNptNNputLaUCAIAwFNAZFJ/Pp7lz5+qNN97Qu+++q379+vm1Dx06VJ06ddKePXusZdXV1aqpqZHT6ZQkOZ1OVVVVqb6+3upTXl4uu92ujIyMGzkWAADQQQR0BqWwsFClpaV666231L17d+uekbi4OHXp0kVxcXGaMWOGioqKlJCQILvdrscee0xOp1PDhw+XJOXk5CgjI0NTp07V8uXL5Xa7tWjRIhUWFnKWBAAASAowoKxZs0aSNHLkSL/lr732mh599FFJ0ooVKxQZGamCggJ5vV7l5uZq9erVVt+oqCiVlZVpzpw5cjqd6tq1q6ZPn66lS5fe2JEAAIAOI6CA8k1emdK5c2etWrVKq1atum6fPn36aMeOHYHsGgAAfIvwWzwAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHECDij79u3TuHHjlJKSooiICL355pt+7Y8++qgiIiL8pjFjxvj1OXfunKZMmSK73a74+HjNmDFDFy9evKEDAQAAHUfAAaWxsVGDBg3SqlWrrttnzJgxOnv2rDX95je/8WufMmWKjh07pvLycpWVlWnfvn2aNWtW4NUDAIAOKTrQFfLy8pSXl/eVfWw2mxwOxzXb/vjHP2rXrl06fPiwhg0bJkl6+eWXNXbsWL344otKSUkJtCQAANDBBOUelL179yoxMVF333235syZoy+++MJqc7lcio+Pt8KJJGVnZysyMlIHDx4MRjkAACDMBHwG5euMGTNGEydOVL9+/XTq1Ck99dRTysvLk8vlUlRUlNxutxITE/2LiI5WQkKC3G73Nbfp9Xrl9XqteY/H095lAwAAg7R7QJk0aZL174EDByozM1O333679u7dq9GjR7dpmyUlJVqyZEl7lQgAAAwX9MeMb7vtNvXs2VMnT56UJDkcDtXX1/v1uXz5ss6dO3fd+1aKi4vV0NBgTbW1tcEuGwAAhFDQA8qnn36qL774QsnJyZIkp9Op8+fPq7Ky0urz7rvvqrW1VVlZWdfchs1mk91u95sAAEDHFfAlnosXL1pnQyTp9OnTOnLkiBISEpSQkKAlS5aooKBADodDp06d0k9+8hPdcccdys3NlST1799fY8aM0cyZM7V27Vo1Nzdr7ty5mjRpEk/wAAAASW04g/LBBx9oyJAhGjJkiCSpqKhIQ4YM0eLFixUVFaWjR4/qBz/4ge666y7NmDFDQ4cO1XvvvSebzWZtY9OmTUpPT9fo0aM1duxYPfDAA/qP//iP9jsqAAAQ1gI+gzJy5Ej5fL7rtu/evftrt5GQkKDS0tJAdw0AAL4l+C0eAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGCcgAPKvn37NG7cOKWkpCgiIkJvvvmmX7vP59PixYuVnJysLl26KDs7Wx999JFfn3PnzmnKlCmy2+2Kj4/XjBkzdPHixRs6EAAA0HEEHFAaGxs1aNAgrVq16prty5cv18qVK7V27VodPHhQXbt2VW5uri5dumT1mTJlio4dO6by8nKVlZVp3759mjVrVtuPAgAAdCjRga6Ql5envLy8a7b5fD699NJLWrRokcaPHy9J+tWvfqWkpCS9+eabmjRpkv74xz9q165dOnz4sIYNGyZJevnllzV27Fi9+OKLSklJuYHDAQAAHUG73oNy+vRpud1uZWdnW8vi4uKUlZUll8slSXK5XIqPj7fCiSRlZ2crMjJSBw8evOZ2vV6vPB6P3wQAADqudg0obrdbkpSUlOS3PCkpyWpzu91KTEz0a4+OjlZCQoLV52+VlJQoLi7OmlJTU9uzbAAAYJiweIqnuLhYDQ0N1lRbWxvqkgAAQBC1a0BxOBySpLq6Or/ldXV1VpvD4VB9fb1f++XLl3Xu3Dmrz9+y2Wyy2+1+EwAA6LjaNaD069dPDodDe/bssZZ5PB4dPHhQTqdTkuR0OnX+/HlVVlZafd599121trYqKyurPcsBAABhKuCneC5evKiTJ09a86dPn9aRI0eUkJCgtLQ0zZs3T88//7zuvPNO9evXT08//bRSUlI0YcIESVL//v01ZswYzZw5U2vXrlVzc7Pmzp2rSZMm8QQPAACQ1IaA8sEHH+j73/++NV9UVCRJmj59ujZs2KCf/OQnamxs1KxZs3T+/Hk98MAD2rVrlzp37myts2nTJs2dO1ejR49WZGSkCgoKtHLlynY4HAAA0BFE+Hw+X6iLCJTH41FcXJwaGhq4H6WD6fvk9lCX8I19siw/1CUARgunz7PEZ/pmCOT7Oyye4gEAAN8uBBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYJzrUBQAAYIK+T24PeJ1PluUHoRJInEEBAAAGIqAAAADjcIkHQdGWU6UAAFzBGRQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYJx2DyjPPvusIiIi/Kb09HSr/dKlSyosLFSPHj3UrVs3FRQUqK6urr3LAAAAYSwoZ1DuuecenT171pref/99q23+/Pnatm2btmzZooqKCp05c0YTJ04MRhkAACBMBeW3eKKjo+VwOK5a3tDQoHXr1qm0tFSjRo2SJL322mvq37+/Dhw4oOHDhwejHAAAEGaCcgblo48+UkpKim677TZNmTJFNTU1kqTKyko1NzcrOzvb6puenq60tDS5XK7rbs/r9crj8fhNAACg42r3gJKVlaUNGzZo165dWrNmjU6fPq3vfe97unDhgtxut2JiYhQfH++3TlJSktxu93W3WVJSori4OGtKTU1t77IBAIBB2v0ST15envXvzMxMZWVlqU+fPvrtb3+rLl26tGmbxcXFKioqsuY9Hg8hBQCADizojxnHx8frrrvu0smTJ+VwONTU1KTz58/79amrq7vmPStX2Gw22e12vwkAAHRcQQ8oFy9e1KlTp5ScnKyhQ4eqU6dO2rNnj9VeXV2tmpoaOZ3OYJcCAADCRLtf4nniiSc0btw49enTR2fOnNEzzzyjqKgoTZ48WXFxcZoxY4aKioqUkJAgu92uxx57TE6nkyd4AACApd0DyqeffqrJkyfriy++UK9evfTAAw/owIED6tWrlyRpxYoVioyMVEFBgbxer3Jzc7V69er2LgMAAISxdg8omzdv/sr2zp07a9WqVVq1alV77xoAAHQQ/BYPAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgnOhQFwAAMF/fJ7eHugR8y3AGBQAAGIczKEAbtfUvyk+W5bdzJQDQ8XAGBQAAGIeAAgAAjMMlHnwtbo4DANxsBBQA+BbhDw6ECwIKAABtxM3ywUNAAW6ym/kXLP8JAghXIQ0oq1at0s9//nO53W4NGjRIL7/8sr7zne+EsqSbjtOtAABcLWQB5fXXX1dRUZHWrl2rrKwsvfTSS8rNzVV1dbUSExNDVRbQoYRDAOYsD76N+Gx+vZAFlF/84heaOXOm/umf/kmStHbtWm3fvl3r16/Xk08+GaqyAOCmC4cvK+BmC0lAaWpqUmVlpYqLi61lkZGRys7Olsvluqq/1+uV1+u15hsaGiRJHo8nKPUNeGZ3ULYL4Gpp87eEugQA1xCM79gr2/T5fF/bNyQB5fPPP1dLS4uSkpL8liclJenEiRNX9S8pKdGSJUuuWp6amhq0GgEA+DaLeyl4275w4YLi4uK+sk9YPMVTXFysoqIia761tVXnzp1Tjx49FBEREcLKvhmPx6PU1FTV1tbKbreHupwOhbENHsY2eBjb4GFsg6c9xtbn8+nChQtKSUn52r4hCSg9e/ZUVFSU6urq/JbX1dXJ4XBc1d9ms8lms/kti4+PD2aJQWG32/nABAljGzyMbfAwtsHD2AbPjY7t1505uSIkv8UTExOjoUOHas+ePday1tZW7dmzR06nMxQlAQAAg4TsEk9RUZGmT5+uYcOG6Tvf+Y5eeuklNTY2Wk/1AACAb6+QBZQf/vCH+uyzz7R48WK53W4NHjxYu3btuurG2Y7AZrPpmWeeueoyFW4cYxs8jG3wMLbBw9gGz80e2wjfN3nWBwAA4CYKyT0oAAAAX4WAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAK7r9OnTunz5cqjL6JAY1+DiAdXwR0AJguPHj+tHP/qRhgwZouTkZCUnJ2vIkCH60Y9+pOPHj4e6vLB29uxZ/frXv9aOHTvU1NTk19bY2KilS5eGqLKO6e6779ZHH30U6jLC2q5du1RVVSXpL2/Mfu6553TrrbfKZrOpd+/eWrZsGV+mbeT1evXEE09oxIgR+tnPfiZJev7559WtWzd1795djzzySNB+9f7byOv1yuv13rT98R6UdrZz505NmDBB9957r3Jzc60Xz9XV1am8vFyVlZV66623lJubG+JKw8/hw4eVk5Oj1tZWNTc369Zbb9Wbb76pe+65R9JfxjglJUUtLS0hrjT8TJw48ZrL33rrLY0aNUrdu3eXJG3duvVmltUhpKen65VXXtH3vvc9lZSU6F//9V/1//7f/1P//v1VXV2tkpISzZ8/XwsXLgx1qWGnqKhIr7/+uiZPnqwdO3bo+9//vsrKyvTCCy8oMjJSixcvVl5enlauXBnqUsNWeXm5VqxYIZfLZYU9u90up9OpoqIiZWdnB23fBJR2NmjQII0fP/66f8k/++yz2rp1q44ePXqTKwt/Dz74oFJTU/Xqq6+qsbFRCxcu1G9/+1uVl5dryJAhBJQbEBkZqREjRqhfv35+y3/1q1/pBz/4gfXjnK+99loIqgtvnTt31p/+9CelpaVp4MCBWrx4sf7hH/7Bat++fbvmzZvHmao2SEtL0/r165Wdna2PP/5Yd955p7Zu3arx48dL+suX68yZM/XJJ5+EttAwtXHjRv3Lv/yLHn744av+4H777bf1u9/9TuvWrdPUqVODU4AP7apz586+EydOXLf9xIkTvs6dO9/EijqOW265xVddXe23rKSkxHfLLbf4Dh065HO73b7IyMgQVRfefvOb3/h69+7tW79+vd/y6Oho37Fjx0JUVceQnJzsc7lcPp/P50tKSvL9/ve/92v/05/+5OvSpUsoSgt7Xbp08f35z3+25jt16uT78MMPrfnTp0/7YmNjQ1Fah3DnnXf6/u3f/u267atWrfLdcccdQds/96C0s759+2r79u3Xbd++fbv69OlzEyvqWC5duuQ3/+STT+qpp55STk6O9u/fH6Kqwt+kSZP03nvvad26dSooKND//u//hrqkDuPv//7v9dOf/lQtLS0aP368Vq9e7XfPycsvv6zBgweHrsAwlpaWJpfLJekvl4AjIiJ06NAhq/3gwYO69dZbQ1Ve2KupqfnKSzijR4/Wp59+GrT9h+zHAjuqpUuX6pFHHtHevXuVnZ3td0psz5492rVrl0pLS0NcZXgaMGCA9u/fr8zMTL/lTzzxhFpbWzV58uQQVdYx9O3bV/v27dOSJUs0aNAgvfLKK4qIiAh1WWHvhRdeUHZ2ttLT0+V0OrVlyxaVl5frrrvu0smTJ3Xu3Dnt3r071GWGpdmzZ+vRRx/Vq6++qsrKSr344ot66qmndOLECUVGRmrNmjV6/PHHQ11m2Lrnnnu0bt06LV++/Jrt69evV0ZGRtD2zz0oQbB//36tXLlSLpdLbrdbkuRwOOR0OvXjH/9YTqczxBWGp1dffVUVFRX6z//8z2u2/+xnP9PatWt1+vTpm1xZx/P+++9r2rRp+vOf/6yqqqqg/if0bdDc3Kx169Zp27Zt+vjjj9Xa2qrk5GTdf//9mjNnjnr37h3qEsNWaWmpXC6Xvvvd72ry5Mnau3evFi9erC+//FLjxo3T008/rchILha0xd69e/XQQw/ptttuu+Yf3B9//LG2b9+uESNGBGX/BBQA13Tx4kWdOnVK/fv3V0xMTKjLARACn3zyidasWaMDBw5c9Qf37Nmz1bdv36Dtm4ACAACMw3mvm+ypp57SP//zP4e6jA6JsQ0exjZ4GNvgYWzDGwHlJvv00095Jj9IGNvgYWyDh7ENHsY2uKZPn65Ro0YFbftc4gEAAAErLi6W2+0O2gscCShB8Pnnn2v9+vVXPcXz3e9+V48++qh69eoV4grDF2MbPIxt8DC2wcPYdlwElHZ2+PBh5ebmKjY29pqPZX355ZfavXu3hg0bFuJKww9jGzyMbfAwtsHD2IZWbW2tnnnmGa1fvz4o2yegtLPhw4dr0KBBWrt27VUvufL5fJo9e7aOHj1qvf0Q3xxjGzyMbfAwtsHD2IbW//zP/+jee+8N2u+fEVDaWZcuXfSHP/xB6enp12w/ceKEhgwZov/7v/+7yZWFP8Y2eBjb4GFsg4exDa7/+q//+sr2jz/+WI8//njQAgqvum9nDodDhw4duu4H5tChQ9ZpSASGsQ0exjZ4GNvgYWyDa8KECYqIiNBXnccI5s9hEFDa2RNPPKFZs2apsrJSo0ePvuqa6CuvvKIXX3wxxFWGJ8Y2eBjb4GFsg4exDa7k5GStXr1a48ePv2b7kSNHNHTo0OAVELTfSf4W27x5sy8rK8sXHR3ti4iI8EVERPiio6N9WVlZvtdffz3U5YU1xjZ4GNvgYWyDh7ENnnHjxvmefvrp67YfOXLEFxEREbT9cw9KEDU3N+vzzz+XJPXs2VOdOnUKcUUdB2MbPIxt8DC2wcPYtr/33ntPjY2NGjNmzDXbGxsb9cEHH+jv/u7vgrJ/AgoAADAOr7oHAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIzz/wH+XvZWWpUyWAAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "phases_counts = dict(\n",
    "    (sampled_state.state[\"phase_reg\"], sampled_state.shots)\n",
    "    for sampled_state in res[0].value.parsed_counts\n",
    ")\n",
    "plt.bar(phases_counts.keys(), phases_counts.values(), width=0.1)\n",
    "plt.xticks(rotation=90)\n",
    "print(\"phase with max probability: \", max(phases_counts, key=phases_counts.get))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08319831-bf54-4892-a623-b7ce1c9b8488",
   "metadata": {},
   "source": [
    "From the phase we can extract the number of solutions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d6a77c5d-c684-40e7-97ef-ec73ce659535",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.783180Z",
     "iopub.status.busy": "2024-05-07T14:36:56.782711Z",
     "iopub.status.idle": "2024-05-07T14:36:56.786670Z",
     "shell.execute_reply": "2024-05-07T14:36:56.786019Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of solutions:  6.439277423870974\n"
     ]
    }
   ],
   "source": [
    "solutions_ratio_qpe = np.sin(np.pi * max(phases_counts, key=phases_counts.get)) ** 2\n",
    "print(\n",
    "    \"Number of solutions: \",\n",
    "    (2**DOMAIN_SIZE) * solutions_ratio_qpe,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8efaff8-3114-429b-ab20-fdff96246ea7",
   "metadata": {},
   "source": [
    "## Amplitude Estimation using Iterative Quantum Amplitude Estimation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6518bf7-acec-4fde-8612-35c2fe73c02f",
   "metadata": {},
   "source": [
    "Now we are ready for the iterative method! \n",
    "\n",
    "Instead of QPE, the algorithm applies the unitary:\n",
    "$$\n",
    "(Q)^mA\n",
    "$$\n",
    "where $m$, the number of repetitions is changed between iterations of the algorithm.\n",
    "\n",
    "There is one subtlety that will change the way we work with the Grover operator. The classical algorithm expects additional indicator qubit that marks the \"good\" states, i.e.:\n",
    "$$\n",
    "|a\\rangle|b\\rangle|f(a,b)\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16c1a7bf-77d4-4e13-9b9b-249a78b750f1",
   "metadata": {},
   "source": [
    "So now, most of our logic will go into the state preparation oracle ($A$). It will combine both the loading of the solution space, and the setting of the indicator qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1145cff0-8dc2-44ab-9f13-28d0d62292a7",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.789303Z",
     "iopub.status.busy": "2024-05-07T14:36:56.788860Z",
     "iopub.status.idle": "2024-05-07T14:36:56.792596Z",
     "shell.execute_reply": "2024-05-07T14:36:56.791989Z"
    }
   },
   "outputs": [],
   "source": [
    "@qfunc\n",
    "def iqae_state_preparation(a: QNum, b: QNum, res: QBit):\n",
    "    reg = QArray(\"reg\")\n",
    "    bind([a, b, res], reg)\n",
    "    hadamard_transform(reg[0:DOMAIN_SIZE])\n",
    "    bind(reg, [a, b, res])\n",
    "    arith_equation(a, b, res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4afdfd8-507c-43e1-9440-ae94df4dbf22",
   "metadata": {},
   "source": [
    "Now, as we use the indicator qubit, the oracle is very simple - it is just a $Z$ gate on the indicator qubit!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "224c78d7-6710-4791-aabf-859a5964dcbc",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.795008Z",
     "iopub.status.busy": "2024-05-07T14:36:56.794554Z",
     "iopub.status.idle": "2024-05-07T14:36:56.797722Z",
     "shell.execute_reply": "2024-05-07T14:36:56.797099Z"
    }
   },
   "outputs": [],
   "source": [
    "iqae_oracle = lambda x: Z(x[x.len - 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f60aaf52-f776-4290-9393-500d9fc0fe6b",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Wrapping all to the Iterative Quantum Amplitude Estimation Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25068d2f-b875-4678-9f18-3f112c2c7c69",
   "metadata": {},
   "source": [
    "The circuit starts with the state $A|0\\rangle$, then applies iterations of the Grover operator. \n",
    "\n",
    "Notice that the algorithm applies varied number of grover iterations on each execution. The number of iterations is chosen dynamically based on previous execution results, using statistical inference methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "324aa3ba-a757-47d9-b365-3699fef9b8e2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.799889Z",
     "iopub.status.busy": "2024-05-07T14:36:56.799716Z",
     "iopub.status.idle": "2024-05-07T14:36:56.803902Z",
     "shell.execute_reply": "2024-05-07T14:36:56.803307Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import CInt, power\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_iqae_algorithm(\n",
    "    k: CInt,\n",
    "    oracle_operand: QCallable[QArray[QBit]],\n",
    "    sp_operand: QCallable[QArray[QBit]],\n",
    "    x: QArray[QBit],\n",
    "):\n",
    "    sp_operand(x)\n",
    "    power(k, lambda: my_grover_operator(oracle_operand, sp_operand, x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a318dfd7-e84e-408f-8ceb-509ee78196b0",
   "metadata": {},
   "source": [
    "We use the built-in `iqae` classical execution code. It assumes only one output to the circuit, which is the indicator qubit.\n",
    "We set $\\epsilon = 1/{2^4} \\cdot 0.5 = 1/32$. `alpha` is the tail probability of esimtating the result with accuracy $\\epsilon$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "85f99785-3da4-4dbf-9535-e32698d81431",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.806048Z",
     "iopub.status.busy": "2024-05-07T14:36:56.805875Z",
     "iopub.status.idle": "2024-05-07T14:36:56.811981Z",
     "shell.execute_reply": "2024-05-07T14:36:56.811409Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import cfunc\n",
    "from classiq.qmod import QConstant, bind\n",
    "from classiq.qmod.builtins.classical_execution_primitives import iqae, save\n",
    "\n",
    "DOMAIN_SIZE_QCONST = QConstant(\"DOMAIN_SIZE_QCONST\", int, DOMAIN_SIZE)\n",
    "\n",
    "\n",
    "@cfunc\n",
    "def cmain():\n",
    "    iqae_res = iqae(epsilon=1 / ((2**DOMAIN_SIZE_QCONST) * 2), alpha=0.01)\n",
    "    save({\"iqae_res\": iqae_res})\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(\n",
    "    k: CInt,\n",
    "    ind_reg: Output[QBit],\n",
    ") -> None:\n",
    "    full_reg = QArray(\"full_reg\")\n",
    "    allocate(DOMAIN_SIZE + 1, full_reg)\n",
    "    my_iqae_algorithm(\n",
    "        k,\n",
    "        iqae_oracle,\n",
    "        lambda x: iqae_state_preparation(\n",
    "            x[0:A_SIZE], x[A_SIZE : x.len - 1], x[x.len - 1]\n",
    "        ),\n",
    "        full_reg,\n",
    "    )\n",
    "    state_reg = QArray(\"state_reg\", length=DOMAIN_SIZE)\n",
    "    bind(full_reg, [state_reg, ind_reg])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fe2254c-5fe2-48e3-b2cd-825d71dbcbf6",
   "metadata": {},
   "source": [
    "### Synthesize the model to a quantum program"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b127fa25-1285-49f4-9fe3-43a57f984d2d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:36:56.814377Z",
     "iopub.status.busy": "2024-05-07T14:36:56.814004Z",
     "iopub.status.idle": "2024-05-07T14:37:02.352678Z",
     "shell.execute_reply": "2024-05-07T14:37:02.351953Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/25d45312-0499-496b-915b-5a054f17b36e?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import Constraints, create_model, show, synthesize, write_qmod\n",
    "\n",
    "constraints = Constraints(optimization_parameter=\"width\")\n",
    "qmod_iqae = create_model(\n",
    "    main,\n",
    "    constraints=constraints,\n",
    "    classical_execution_function=cmain,\n",
    ")\n",
    "\n",
    "write_qmod(qmod_iqae, \"quantum_counting_iqae\")\n",
    "qprog_iqae = synthesize(qmod_iqae)\n",
    "show(qprog_iqae)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a468ad77-ace5-4ee5-a8fe-5cb5bfe4342f",
   "metadata": {},
   "source": [
    "### Quantum Program execution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c1110098-1af8-4c2a-9ca7-14b8d36e75f3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:37:02.357504Z",
     "iopub.status.busy": "2024-05-07T14:37:02.356411Z",
     "iopub.status.idle": "2024-05-07T14:37:03.946488Z",
     "shell.execute_reply": "2024-05-07T14:37:03.945789Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IQAE result: 0.3798699353077861, confidence interval: (0.3547029869901588, 0.4050368836254135)\n"
     ]
    }
   ],
   "source": [
    "from classiq import execute\n",
    "\n",
    "res = execute(qprog_iqae).result()\n",
    "\n",
    "iqae_res = res[0].value\n",
    "print(\n",
    "    f\"IQAE result: {iqae_res.estimation}, confidence interval: {iqae_res.confidence_interval}\"\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1aa562ff-5fb9-45d7-ba20-ef15f59c72d8",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:37:03.948945Z",
     "iopub.status.busy": "2024-05-07T14:37:03.948564Z",
     "iopub.status.idle": "2024-05-07T14:37:03.952200Z",
     "shell.execute_reply": "2024-05-07T14:37:03.951537Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of solutions: 6.077918964924578, accuracy: 0.8053423461640756\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    f\"Number of solutions: {(2**DOMAIN_SIZE) * iqae_res.estimation}, accuracy: \"\n",
    "    f\"{(2**DOMAIN_SIZE)*(iqae_res.confidence_interval[1]-iqae_res.confidence_interval[0])}\"\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5b92fe20-80e6-45be-9602-9d1b42a6838b",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:37:03.954663Z",
     "iopub.status.busy": "2024-05-07T14:37:03.954179Z",
     "iopub.status.idle": "2024-05-07T14:37:03.957943Z",
     "shell.execute_reply": "2024-05-07T14:37:03.957375Z"
    }
   },
   "outputs": [],
   "source": [
    "assert np.isclose(\n",
    "    iqae_res.estimation, solutions_ratio_qpe, 1 / ((2**DOMAIN_SIZE) * 0.5)\n",
    ")\n",
    "assert np.isclose(\n",
    "    iqae_res.estimation, 6 / (2**DOMAIN_SIZE), 1 / ((2**DOMAIN_SIZE) * 0.5)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20521d41-464a-4370-a3d9-2d8e26f14677",
   "metadata": {},
   "source": [
    "We can also see the statistics of the IQAE execution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ed5757d5-0768-44cd-9301-02b5c464b144",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:37:03.960337Z",
     "iopub.status.busy": "2024-05-07T14:37:03.959912Z",
     "iopub.status.idle": "2024-05-07T14:37:03.963658Z",
     "shell.execute_reply": "2024-05-07T14:37:03.963049Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration_id: 0, num grover iterations: 0, counts: {'0': 624, '1': 376}\n",
      "iteration_id: 1, num grover iterations: 1, counts: {'0': 171, '1': 829}\n"
     ]
    }
   ],
   "source": [
    "for i, iteration in enumerate(iqae_res.iterations_data):\n",
    "    print(\n",
    "        f\"iteration_id: {i}, num grover iterations: {iteration.grover_iterations}, counts: {iteration.sample_results.counts}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66648b44-71d9-47d8-9756-3faea9474745",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "<a name='QCWiki'>[1]</a>: [Quantum Counting Algorithm Wikipedia](https://en.wikipedia.org/wiki/Quantum_counting_algorithm)\n",
    "\n",
    "<a name='IQAE'>[2]</a>: [Grinko, D., Gacon, J., Zoufal, C. et al. Iterative quantum amplitude estimation. npj Quantum Inf 7, 52 (2021)](https://doi.org/10.1038/s41534-021-00379-1)\n",
    "\n",
    "<a name='AE'>[3]</a>: [Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2002). Quantum Amplitude Amplification and Estimation. Contemporary Mathematics, 305, 53-74.](https://arxiv.org/abs/quant-ph/0005055)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
